package difficult.t37.solveSudoku;


import java.util.ArrayList;
import java.util.List;

/**
 * https://leetcode-cn.com/problems/sudoku-solver/
 * 给出数独的一个解
 * 使用回溯法找到数独的解
 * 执行用时：9 ms, 在所有 Java 提交中击败了22.57%的用户
 * 内存消耗：35.8 MB, 在所有 Java 提交中击败了56.62%的用户
 *
 * @Author luxiaoxiao
 * @Date 2022/1/9
 */
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        char[][] board = {
                {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
                {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
                {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
                {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
                {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
                {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
                {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
                {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
                {'.', '.', '.', '.', '8', '.', '.', '7', '9'}
        };
        solution.solveSudoku(board);
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.print(board[i][j]);
                System.out.print("  ");
            }
            System.out.println();
        }
        System.out.println(solution.flag);
    }

    /**
     * 标志着当前数独是否解开
     */
    private boolean flag = false;

    /**
     * 给出数独的一个解
     *
     * @Author luxiaoxiao
     * @Date 2022/1/9
     */
    public void solveSudoku(char[][] board) {
        // 判断数独是否已经填满数字，如果已经填满数字，则直接返回，如果数独没有填满，则填写一个数字后进行递归
        if (notEmpty(board)) {
            flag = true;
            return;
        }

        // 查找下一个未填充数字的位置
        int m = 0;
        int n = 0;
        loop: for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    m = i;
                    n = j;
                    break loop;
                }
            }
        }

        // 填写一个位置
        for (char k = '1'; k <= '9'; k++) {
            board[m][n] = k;
            if (isValidSudoku(board, m, n)) {
                solveSudoku(board);
                if (flag) {
                    return;
                } else {
                    board[m][n] = '.';
                }
            } else {
                board[m][n] = '.';
            }
        }
    }


    /**
     * 判断数独是否已经填满了数字
     *
     * @Author luxiaoxiao
     * @Date 2022/1/10
     */
    public boolean notEmpty(char[][] board) {
        for (char[] chars : board) {
            for (char aChar : chars) {
                if (aChar == '.') {
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * 判断加入新的元素后数独是否仍然合法（不是指是否有解）
     *
     * @param i 新加入元素的横坐标
     * @param j 新加入元素的纵坐标
     * @Author luxiaoxiao
     * @Date 2022/1/9
     */
    public boolean isValidSudoku(char[][] board, int i, int j) {
        char newElement = board[i][j];

        // 检查行数据是否有重复
        char[] chars = board[i];
        for (int m = 0; m < 9; m++) {
            if (m == j) {
                continue;
            }
            char aChar = chars[m];
            if (aChar == newElement) {
                return false;
            }
        }

        // 检查列数据是否有重复
        for (int m = 0; m < 9; m++) {
            if (m == i) {
                continue;
            }
            char aChar = board[m][j];
            if (aChar == newElement) {
                return false;
            }
        }

        // 检查块中是否有重复
        for (int m = i / 3 * 3; m < i / 3 * 3 + 3; m++) {
            for (int n = j / 3 * 3; n < j / 3 * 3 + 3; n++) {
                if (m == i || n == j) {
                    continue;
                }
                char aChar = board[m][n];
                if (aChar == newElement) {
                    return false;
                }
            }
        }

        return true;
    }
}
